package 机试题16年;

/**
 * Created by hest0 on 2017/4/18.
 */
public class 小米Git {
    public static void main(String[] args) {

    }

    public class Solution {

        //开始
        public int getSplitNode(String[] matrix, int indexA, int indexB) {
            if (indexA == indexB) return indexA;

            int nodeNum = matrix.length;

            //数据容器
            int tree[] = new int[nodeNum];
            boolean flag[] = new boolean[nodeNum];

            //tree初始化为自然数
            for (int i = 0; i < tree.length; i++) {
                tree[i] = i;
            }

            //填充tree
            dfs(0, tree, matrix);

            int idxa = indexA;
            int idxb = indexB;

            //被dfs的填充过，flag设置true
            while (tree[idxa] != idxa) {
                flag[idxa] = true;
                idxa = tree[idxa];
            }

            //没有被dfs填充过，idxb
            while (tree[idxb] != idxb) {
                if (flag[idxb]) {
                    break;
                }
                idxb = tree[idxb];
            }

            return idxb;
        }

        //递归，填充的是tree
        private void dfs(int root, int[] tree, String[] matrix) {
            for (int i = 0; i < tree.length; ++i) {
                if (matrix[root].charAt(i) == '1' && tree[i] == i && i != 0) {
                    tree[i] = root;
                    dfs(i, tree, matrix);
                }
            }
        }
        //结束
    }

}
